/*
 * grafo.c
 *
 *  Created on: 23/09/2011
 *      Author: alexsander
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>


#define BRANCO 0
#define CINZA  1
#define PRETO  2
#define BFS 0
#define DFS 1
#define INF 4294967295U
#define PARADA -1

typedef struct _vertice Vertice;
typedef struct bloco Bloco;
typedef struct fila Fila;

struct _vertice
{
	Fila *adjacentes;
	unsigned int descricao;
	struct _vertice* phi;
	unsigned int cor;
	unsigned int d;
	unsigned int f;
};

struct bloco
{
	Vertice *vertice;
	struct bloco *proximo;
};

struct fila
{
	Bloco* cabeca;
	Bloco* cauda;
};

typedef struct
{
	Fila* vertices;
} Grafo;


void enfileirar (Fila*, Vertice*);
Vertice* desenfileirar (Fila*);
int filaVazia (Fila);
void desalocarFila (Fila*);
Fila* criarFila (void);
Grafo* criarGrafo (Fila*);
Vertice* criarVertice (int);
void imprimirGrafoBusca (Grafo, int);
void imprimirVertice (Vertice, int);
void impVertsDescEnd (Fila);
Grafo* capturarDadosTeclado (void);
Grafo* capturarDadosArq (void);
Vertice* procurarVertice(Fila, int);
void buscaLargura (Grafo*, Vertice*);
void buscaProfundidade (Grafo*);
void visita (Vertice*, unsigned int*);
void exibeMenu (Grafo*);

int main (void){

	Grafo* grafo = NULL;
	exibeMenu (grafo);

	return 0;
}

void exibeMenu (Grafo* grafo){

	int op;

	do {
		printf("\n========================================================\n");
		printf("\t\tBusca em Grafos\n");
		printf("========================================================\n\n");
		printf("(0) - \tCapturar dados do Grafo pelo teclado\n");
		printf("(1) - \tCapturar dados do Grafo por um arquivo\n");
		printf("(2) - \tBusca em Largura\n");
		printf("(3) - \tBusca em Profundidade\n");
		printf("(4) - \tImprimir descricao e endereco dos vertices\n");
		printf("(5) - \tLimpar tela\n");
		printf("(6) - \tSair\n");

		fflush(stdin);
		scanf("%d", &op);

		switch (op){

			case 0:
				//para nao ficar alocando desordenadamente sem liberar o espaco da memoria.
				if (grafo != NULL){
					free (grafo);
					grafo = NULL;
				}
				grafo = capturarDadosTeclado();
				break;
			case 1:
				if (grafo != NULL){
					free (grafo);
					grafo = NULL;
				}
				grafo = capturarDadosArq();
				break;
			case 2:
				if (grafo != NULL){
					buscaLargura(grafo, grafo->vertices->cabeca->vertice); //s nesse caso sera o primeiro elemento da fila.
				}
				else
					printf("Grafo nulo, capture primeiro os dados dele.");
				break;
			case 3:
				if (grafo != NULL)
					buscaProfundidade(grafo);
				else
					printf("Grafo nulo, capture primeiro os dados dele.\n");
				break;
			case 4:
				if (grafo != NULL)
					impVertsDescEnd(*grafo->vertices);
				else
					printf("Grafo nulo, capture primeiro os dados dele.\n");
				break;
			case 5:
				//system("cls");
				system("clear");
				break;
		}

	} while (op != 6);

	if (grafo != NULL)
		desalocarFila(grafo->vertices);
	free(grafo);

	printf("\nMemoria alocada no uso do programa liberada pressione <Enter> para sair.");
	fflush(stdin);
	getchar();
}

Grafo* capturarDadosTeclado (){

	Fila* fila = criarFila();
	Fila* filaAdj;
	Grafo* grafo;
	Vertice *vAux;
	Bloco* bAux;
	int qtd = 0, contador, contador2 = 0;
	unsigned int endV;

	if (fila != NULL){

		printf("\nEntre com a quantidade de vertices: ");
		scanf ("%d", &qtd);

		for (contador = 0; contador < qtd; contador++){
			vAux = criarVertice(contador);
			if (vAux!= NULL)
				enfileirar(fila, vAux);
		}

		printf("\n------------------------------------");
		printf("\n\n\tCodigo dos vertices: ");
		impVertsDescEnd(*fila);

		bAux = fila->cabeca;
		do{
			filaAdj = criarFila();
			endV = 0; contador2 = 0;
			printf ("\n\nDigite o endereco dos vertices adjacentes ao vertice:\nDescricao: %d - Endereco: %d\n(Para parar insira: %d)\n", bAux->vertice->descricao, (unsigned int)bAux->vertice,PARADA);

			do {
				scanf ("%d", &endV);
				if (endV != PARADA){
					vAux = (Vertice*)endV;
					enfileirar(filaAdj, vAux);
				}
				contador2++;
			} while ((endV != PARADA) && (contador2 < qtd-1));

			bAux->vertice->adjacentes = filaAdj;
			bAux = bAux->proximo;
		} while (bAux != NULL);

		grafo = criarGrafo(fila);
		return grafo;
	}

	return NULL;
}

Grafo* capturarDadosArq (void){

	Grafo* grafo;
	Fila* fila = criarFila();
	Fila* filaAdj;
	Vertice* verticeAux, *vAuxAdj;
	char* cadeiaAux;
	int qtdVertices = 0, contador = 0, desc = 0;
	FILE* f;
	char path[150];

	printf ("\n\nDigite o caminho do arquivo (150 caracteres no máximo): ");
	fflush(stdin);
	scanf("%s", path);

	f = fopen (path, "r");
	if (f != NULL){

		//Cria os vértices
		cadeiaAux = (char*) malloc (sizeof (char));
		while (!feof(f)){

			if (qtdVertices == 0)
				fgets(cadeiaAux, 2, f);
			contador = desc = 0;

			if ((cadeiaAux[0] == '\n') || (qtdVertices == 0)){

				if (qtdVertices != 0)
					fgets(cadeiaAux, 2, f);

				if ((cadeiaAux[0] != '\n') && (cadeiaAux[0] != '\0')){


					while ((cadeiaAux[0] != '\t') && (cadeiaAux[0] != '\n') && (cadeiaAux[0] != '\0')){
						desc *= pow(10, contador);
						desc += (cadeiaAux[0] - 48);
						contador++;
						fgets (cadeiaAux, 2, f);
					}

					if ((verticeAux = procurarVertice(*fila, desc)) == NULL){
						qtdVertices++;
						verticeAux = criarVertice(desc);
						enfileirar(fila, verticeAux);
						filaAdj = criarFila();
						verticeAux->adjacentes = filaAdj;
					}
				}
			}

			//Captura os vertices adjacentes
			else{
				if (cadeiaAux[0] == '\t'){

					fgets(cadeiaAux, 2, f);

					if ((cadeiaAux[0] != '\n') && (cadeiaAux[0] != '\0')){

						while ((cadeiaAux[0] != '\t') && (cadeiaAux[0] != '\n') && (cadeiaAux[0] != '\0')){
							desc *= pow(10, contador);
							desc += (cadeiaAux[0] - 48);
							contador++;
							fgets (cadeiaAux, 2, f);
						}

						if ((vAuxAdj = procurarVertice(*fila, desc)) == NULL){
							qtdVertices++;
							vAuxAdj = criarVertice(desc);
							enfileirar(fila, vAuxAdj);
							filaAdj = criarFila();
							vAuxAdj->adjacentes = filaAdj;
						}
						enfileirar(verticeAux->adjacentes, vAuxAdj);
					}
				}
			}
		}

		fclose (f);
		printf("\nGrafo capturado com sucesso!");

		grafo = criarGrafo(fila);
		return grafo;
	}

	printf ("\nNao foi possivel ler arquivo.");

	return NULL;
}

Vertice* procurarVertice(Fila fila, int descricao){

	Bloco* bAux = fila.cabeca;

	while (bAux != NULL){
		if (bAux->vertice->descricao == descricao)
			return bAux->vertice;
		bAux = bAux->proximo;
	}

	return NULL;

}

void buscaLargura (Grafo* grafo, Vertice* s){

	Fila* filaQ = criarFila();
	Bloco* bVAux = grafo->vertices->cabeca->proximo; //Exlcui o s.
	Vertice* uAux;

	while (bVAux != NULL){
		bVAux->vertice->cor = BRANCO;
		bVAux->vertice->d = INF;
		bVAux->vertice->phi = NULL;

		bVAux = bVAux->proximo;
	}


	s->cor = CINZA;
	s->phi = NULL;
	s->d = 0;
	enfileirar(filaQ, s);


	while (!filaVazia(*filaQ)){


		uAux = desenfileirar(filaQ);
		bVAux = uAux->adjacentes->cabeca;

		while (bVAux != NULL){

			if (bVAux->vertice->cor == BRANCO){
				bVAux->vertice->cor = CINZA;
				bVAux->vertice->d = uAux->d + 1;
				bVAux->vertice->phi = uAux;
				enfileirar(filaQ, bVAux->vertice);
			}

			bVAux = bVAux->proximo;
		}

		uAux->cor = PRETO;
	}

	imprimirGrafoBusca(*grafo, BFS);
}

void buscaProfundidade (Grafo* grafo){

	unsigned int tempo = 0;
	Bloco* bVAux = grafo->vertices->cabeca;

	while (bVAux != NULL){
		bVAux->vertice->cor = BRANCO;
		bVAux->vertice->phi = NULL;

		bVAux = bVAux->proximo;
	}


	bVAux = grafo->vertices->cabeca;
	bVAux->vertice->phi = NULL;
	while (bVAux != NULL){

		if (bVAux->vertice->cor == BRANCO)
			visita (bVAux->vertice, &tempo);

		bVAux = bVAux->proximo;
	}

	imprimirGrafoBusca(*grafo, DFS);

}

void visita (Vertice* vAux, unsigned int* tempo){

	Bloco* bUAux;

	vAux->d = ++(*tempo);
	vAux->cor = CINZA;

	bUAux = vAux->adjacentes->cabeca;
	while (bUAux != NULL){

		if (bUAux->vertice->cor == BRANCO){
			bUAux->vertice->phi = vAux;
			visita (bUAux->vertice, tempo);
		}

		bUAux = bUAux->proximo;
	}

	vAux->f = ++(*tempo);
	vAux->cor = PRETO;
}


void enfileirar (Fila* fila, Vertice* vertice){

	Bloco* bloco = (Bloco*) malloc (sizeof(Bloco));
	if (bloco != NULL){
		bloco->vertice = vertice;
		bloco->proximo = NULL;

		if (filaVazia(*fila))
			fila->cabeca = fila->cauda = bloco;
		else{
			fila->cauda->proximo = bloco;
			fila->cauda = bloco;
		}
	}
	else
		printf("\nErro na alocacao de memoria!\n");

}

Vertice* desenfileirar (Fila* fila){

	Vertice* vertice;
	Bloco* aux;

	if (filaVazia(*fila))
		return NULL;

	vertice = fila->cabeca->vertice;

	if (fila->cabeca == fila->cauda){
		fila->cabeca = fila->cauda = NULL;
		free(fila->cabeca);
	}

	else{
		aux = fila->cabeca;
		fila->cabeca = fila->cabeca->proximo;
		free(aux);
	}

	return vertice;

}

int filaVazia (Fila fila){

	return ((&fila == NULL) || (fila.cabeca == NULL));
}


void desalocarFila (Fila* fila){

	Bloco* bloco, *aux;
	bloco = fila->cabeca;

	while (bloco != NULL){
		aux = bloco;
		bloco = bloco->proximo;
		free (aux);
	}

	//free (fila);
	fila->cabeca = fila->cauda = NULL;

}

Fila* criarFila (void){

	Fila* fila = (Fila*) malloc (sizeof(Fila));
	if (fila == NULL){
		printf ("\nErro ao alocar memoria para lista.");
		return NULL;
	}
	fila->cabeca = fila->cauda = NULL;

	return fila;
}

Grafo* criarGrafo (Fila* fila){

	Grafo* grafo = (Grafo*) malloc (sizeof (Grafo));
	if (grafo == NULL)
		printf ("\nErro ao alocar memoria para o grafo.");
	else
		grafo->vertices = fila;

	return grafo;

}

Vertice* criarVertice (int descricao){

	Vertice* vertice = (Vertice*) malloc (sizeof (Vertice));

	if (vertice == NULL){
		printf("\nErro ao criar vertice!");
		return NULL;
	}

	vertice->adjacentes = NULL;
	vertice->cor = BRANCO;
	vertice->phi = NULL;
	vertice->d = INF;
	vertice->f = INF;
	vertice->descricao = descricao;

	return vertice;
}

void imprimirGrafoBusca (Grafo grafo, int tipo){

	if (!filaVazia(*grafo.vertices)){
		Bloco* bloco;
		bloco = grafo.vertices->cabeca;

		while (bloco != NULL){

			if (tipo == DFS){
				printf("\n---------Busca em Profundidade----------\n");
				imprimirVertice(*bloco->vertice, DFS);
				printf("\n-----------------------------------\n");
			}

			else{
				printf("\n---------Busca em Largura----------\n");
				imprimirVertice(*bloco->vertice, BFS);
				printf("\n-----------------------------------\n");
			}
			bloco = bloco->proximo;
		}

	}
	else
		printf("\nGrafo nulo!");
}

void imprimirVertice (Vertice vertice, int tipo){

	if (&vertice == NULL)
		printf("\nVertice vazio!");

	else{
		if (tipo == DFS)
			printf("Vertice: \t%d\nPredecessor: \t%d\nDescoberta: \t%d\nFinalizacao: \t%d", vertice.descricao, (vertice.phi != NULL) ? vertice.phi->descricao : INF, vertice.d, vertice.f);
		else
			printf("Vertice: \t%d\nPredecessor: \t%d\nDistancia: \t%d", vertice.descricao, (vertice.phi != NULL) ? vertice.phi->descricao : INF, vertice.d);
	}

}

void impVertsDescEnd (Fila fila){

	Bloco *bloco = fila.cabeca;

	while (bloco != NULL){
		printf("\nDescricao: %d - Endereco: %d", bloco->vertice->descricao, (unsigned int)bloco->vertice);
		bloco = bloco->proximo;
	}

}
